1. Technical Field
The present invention relates to a method and system for data processing in general, and in particular to a method and system for routing interconnects within an integrated circuit design. Still more particularly, the present invention relates to a method and system for re-routing interconnects within an integrated circuit design having blockages and buffer bays.
2. Description of the Prior Art
As integrated circuits become increasingly smaller, the resistance per unit length of interconnect continues to increase, but the capacitance per unit length of interconnect remains almost constant while logic delay continues to decrease. If this trend continues, interconnect delay will become more dominant than logic delay in the near future.
Generally speaking, the characteristic interconnect delay of an interconnect is directly proportional to the square of the length of the interconnect. One approach to reducing interconnect delay is to insert buffers along the interconnect because buffer insertion effectively divides the interconnect into smaller segments, which makes the interconnect delay almost linear with respect to the length of the interconnect. Hence, buffer insertion has become a necessary step in modern integrated circuit designs.
A Steiner tree algorithm is commonly used to perform interconnect routing, and a buffer insertion algorithm is then used to insert buffers into the previously routed interconnect network. When inserting buffers into a previously routed interconnect network (especially a hierarchical one), a buffer typically cannot be placed on top of a pre-existing circuit macro known as a blockage. Thus, if the interconnect network was routed mostly over one or more blockages, then no buffer insertion algorithm that follows the conventional Steiner tree routing topology will be able to find a solution. Referring now to the drawings and in particular to FIG. 1a, there is illustrated an example of a two-pin net 10 whose Steiner tree route runs over a blockage 11, on top of which buffers cannot be placed. However, if two-pin net 10 is re-routed as shown in FIG. 1b, then buffers, such as b1 and b2, can be judiciously inserted on two-pin net 10, as depicted in FIG. 1c, albeit for an additional wire length cost.
In some design methodologies, instead of trying to restrict buffer insertions to certain locations between large blockages, it may be more suitable to pre-assign certain locations specifically for buffer placements. These pre-assigned locations specifically reserved for buffer placements are known as buffer bays. FIG. 2a shows an example of two-pin net 10 that does not pass through any buffer bays, such as a buffer bay 12, and is totally blocked from buffer insertions. By re-routing two-pin net 10 through buffer bay 12, as shown in FIG. 2b, buffers such as b3 and b4 can be suitably inserted into two-pin net 10, as shown in FIG. 2c. 
The present disclosure provides an improved method and system for intelligently re-routing interconnects within an integrated circuit design that contains blockages and/or buffer bays.
In accordance with a preferred embodiment of the present invention, a net within an integrated circuit design is initially decomposed into multiple two-paths. The net includes interconnects previously routed by utilizing a Steiner tree routing algorithm. Next, a cost associated with each of the two-paths is calculated. A two-path having a high cost is subsequently selected and re-routed with a lower cost two-path.
All objects, features, and advantages of the present invention will become apparent in the following detailed written description.